/*
 * @lc app=leetcode.cn id=35 lang=javascript
 *
 * [35] 搜索插入位置
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
// 二分查找法
var searchInsert = function(nums, target) {
  let n = nums.length
  let right = n - 1
  let left = 0
  let res = n
  while (left <= right) {
    let mid = ((right - left) >> 2) + left
    // 在目标值在中间的左边
    if (target <= nums[mid]) {
      // 如果nums[mid] === target,结果为mid
      // 如果nums[mid] < target，结果为mid
      res = mid
      right = mid - 1
    } else {
      // 如果 target === nums[mid]时，结果为mid
      // 如果target > nums[mid] 时，结果为mid + 1
      // res = mid + 1
      left = mid + 1
    }
  }
  return res
};
// @lc code=end
// 二分查找法要确定不变量，再进行计算
// 确定定义的是闭区间[left, right]
// 返回right + 1
// 还是开区间[left,right)
// 返回right
// 当 nums[pos - 1] < target <= nums[pos]
// var searchInsert = function(nums, target) {
//   let n = nums.length
//   let right = n - 1
//   let left = 0
//   let res = n
//   while (left <= right) {
//     let mid = ((right - left) >> 2) + left
//     // 在目标值在中间的左边
//     if (target < nums[mid]) {
//       right = mid - 1
//     } else if (target > nums[mid]) {
//       left = mid + 1
//     } else {
//       return mid
//     }
//   }
//   return right + 1
// };
// 如果找到目标值之间返回
// 前后并列指针，如果没有找到目标值，并且目标值在并列指针之间，那么返回对应新增下标
// var searchInsert = function(nums, target) {
//   if (nums.length === 1) {
//     return target <= nums[0] ? 0 : 1
//   }
//   let index = 0
//   if (target < nums[0]) return 0
//   while (index < nums.length - 1) {
//     let cur = nums[index]
//     let next = nums[index + 1]
//     if (cur === target) return index
//     if (next === target) return index + 1
//     if (cur < target && target < next) return index + 1
//     index ++
//   }
//   return nums.length
// };

